package leetcode.pre100;

/**
 * <p>
 * 行不用检查，index就是行。
 * 每次给数组array[index]赋值，就要检查是否和以前的同列，是否在对角线。
 * 如{1,2}是在以对角线，后面不用检查了直接pass掉这种可能性。那么就放{1,3}等。
 *
 * 缺点：列总是从0-n-1赋值，还需要判断。
 * 结合{@link Code51_Nqueen1},{@link Code51_Nqueen2}
 *
 * 见{@link Code51_Nqueen3}，每次进行全排列，不需要对列从0-n-1全部赋值，
 * 是在全排列的基础上，当进行到当前位置交换 ，就检查对角线是否满足。
 * 因为行和列肯定满足
 */
public class Code51_Nqueen2 {

    private static int totalCount = 0;

    public static void printNQueen(int n){
        if(n <= 0){
            return;
        }
        //初始值都是0
        int[] array = new int[n];
        process(array,0);
    }

    private static void process(int[] array, int index) {
        //说明0-n-1都通过验证，是正确的摆放方法
        if(index == array.length ){
            totalCount ++;
           // print(leetcode.array);
            return;
        }

        //否则每个位置都进行判断
        //TODO 很多无用的递归 0 0
        for (int i = 0; i < array.length; i++) {
            //对array[index]进行穷举
            array[index] = i;
            //判断是否满足条件，满足则继续 ，不然当前位置改变
            if(check(array,index)){
                process(array,index+1);
            }
        }
    }

    //判断是否在同一列，同一对角线上，是的话，不满足条件
    private static boolean check(int[] array, int index) {

        //前0-index-2肯定不在对角线上了，所以只要判断index-1和 0-index-2是否在对角线上即可
        for (int i = 0; i < index; i++) {
            if (array[i] == array[index]
                    || Math.abs(index - i) == Math.abs(array[index] - array[i])) {
                return false;
            }
        }
        return true;
    }

    //打印皇后摆法数量
    private static void print(int []array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + 1 + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        printNQueen(14);
        //14个用时6.836s
        System.out.println("用时 = " + (System.currentTimeMillis() - start));
        System.out.println("totalCount = " + totalCount);
    }

}
